All Questions
25 questions
6votes
1answer
393views
Condition Number dependent algorithms for matrix operations
Using the Conjugate gradient method we can solve a linear system $Ax=b$, where $A\in\mathbb R^{n\times n}$ in time $O(n^2 \sqrt{\kappa})$, where $\kappa=\frac{\sigma_\mathrm{max}(A)}{\sigma_\mathrm{...
- 958
0votes
0answers
72views
Uniformly redistributing items across bins. What problem is this?
I'm trying to find reading material on a particular problem I'm interested in, but I don't know the terms to search. Problem assumptions/definitions: We have finite number of items I with weights [0, ...
- 101
1vote
0answers
126views
How to measure the weirdness of algorithms?
Let $M$ is a polynomial $k$-tape Turing machine and $C^t(x)$ is a time-bounded Kolmogorov complexity. Let $str_M(x)$ be a string of the following form: $$str_M(x)=w_1^1\# w_2^1 \# ... \# w_{m}^1 ■ w_1^...
- 49
0votes
1answer
73views
Given a partition and an element, find the subset that includes this element
I am interested in the following simple problem: Let $X$ be a set and $X_1\cup X_2\cup\cdots\cup X_k$ be a finite partition of $X$. Given $x\in X$, find the subset $X_i$ for which $x\in X_i$. I am ...
3votes
0answers
147views
Isomorphic subforest problem
I recently read that the following problem is NP-Complete: Given a tree $T$, and a forest $F$, is there a subgraph of $T$ isomorphic to $F$? The reference provide was to the textbook “Computers and ...
- 625
1vote
0answers
119views
Entropy bounds on solutions to problems in BPP and other complexity classes based on entropy demands
Has anyone studied the asymptotics of problems in complexity classes like $BPP$? The thought came to me that if a problem in $BPP$ only requires $O(log(n))$ bits of entropy to solve then, intuitively, ...
- 1,213
8votes
0answers
382views
What exactly did Lenstra prove on mixed integer linear program?
I studied Lenstra's paper https://www.jstor.org/stable/3689168. I have no clue what complexity he provides on Mixed Integer Programming (it is too terse and it is not a stand alone paper as he assumes ...
- 13.5k
10votes
2answers
317views
Complexity of Homogenizing a String
Motivation: While developing tools for data versioning, we ended up looking into algorithms for "diff"ing two sets of integers, by coming up with a sequence of transformations that take one set of ...
3votes
0answers
114views
Notion of "total work" of a problem?
I apologize in advance if this question is outside the scope of this Exchange community; if so, perhaps someone can point me in the right direction. I am curious if there is a theoretical notion of "...
5votes
2answers
296views
Log space algorithms for modular decomposition tree
Can we have log space algorithms for modular decomposition tree (see definition) for any graph? If not, can we have log space algorithms for modular decomposition tree for any particular graph class? ...
- 185
1vote
1answer
153views
How to find the "best vectors" in a given matrix whose sum of products is as small as possible?
The input is a matrix $\mathbf{A}=[a_{ij}]$ of real numbers $a_{ij}>0$ for all $i\in\{1,\ldots,k\}$ and $j\in\{1,\ldots,n\}$ and a real number $v$. The coefficient of the matrix are not all greater ...
- 115
55votes
7answers
5kviews
For which problems in P is it easier to verify the result than to find it?
For (search versions) of NP-complete problems, verifying a solution is clearly easier than finding it, since the verification can be done in polynomial time, while finding a witness takes (probably) ...
- 11.6k
7votes
1answer
142views
Quanitifier Free Presburger Arithmetic: Upper bound on solution size?
DISCLAIMER: I had originally posted this to CS.SE, but I've deleted it and moved it here, since it received little attention, and I think it is a research level question. According to this paper, if ...
- 3,014
9votes
0answers
564views
Is it possible to solve perfect matching in linear time
As we know matching can be solve in polynomial time. One classical and famous algorithm is designed by Karp and Hopcroft. Is it possible to solve perfect matching problem in linear time for given $...
- 99
2votes
1answer
160views
Complexity of determining unique elements of each cycle in a permutation
It is a well known fact that a permutation is a set of cycles, and that one can find all cycles of a permutation in $O(n)$ time, where $n$ is the length of the permutation. But suppose that we know ...
